Grokking LinkedIn Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
LinkedIn Easy
Find Pivot Index (easy)
Solution: Find Pivot Index
Isomorphic Strings (easy)
Solution: Isomorphic Strings
Second Minimum Node In a Binary Tree (easy)
Solution: Second Minimum Node In a Binary Tree
Minimum Time to Type Word Using Special Typewriter (easy)
Solution: Minimum Time to Type Word Using Special Typewriter
Intersection of Two Arrays (easy)
Solution: Intersection of Two Arrays
Can Place Flowers (easy)
Solution: Can Place Flowers
Valid Perfect Square (easy)
Solution: Valid Perfect Square
Maximum Depth (or Height) of Binary Tree (easy)
Solution: Maximum Depth (or Height) of Binary Tree
Sqrt (easy)
Solution: Sqrt
Valid Palindrome (easy)
Solution: Valid Palindrome
LinkedIn Medium
Rotate List (medium)
Solution: Rotate List
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Valid Triangle Number (medium)
Solution: Valid Triangle Number
Valid Parenthesis String (medium)
Solution: Valid Parenthesis String
Edit Distance (medium)
Solution: Edit Distance
Remove All Ones With Row and Column Flips II (medium)
Solution: Remove All Ones With Row and Column Flips II
Reverse Integer (medium)
Solution: Reverse Integer
Triplet Sum to Zero (medium)
Solution: Triplet Sum to Zero
Longest Substring Without Repeating Characters (medium)
Solution: Longest Substring Without Repeating Characters (medium)
Decode Ways (medium)
Solution: Decode Ways
Quadruple Sum to Target (medium)
Solution: Quadruple Sum to Target
Next Permutation (medium)
Solution: Next Permutation
Search in Rotated Array (medium)
Solution: Search in Rotated Array
Word Search (medium)
Solution: Word Search
Remove Nth Node From End of List (Medium)
Solution: Remove Nth Node From End of List
House Robber II (medium)
Solution: House Robber II
Coin Change
Solution: Coin Change
Design Add and Search Words Data Structure (medium)
Solution: Design Add and Search Words Data Structure
Merge Intervals (medium)
Solution: Merge Intervals
Number of Islands (easy)
Solution: Number of Islands
Longest Palindromic Subsequence (medium)
Solution: Longest Palindromic Subsequence
Kth Smallest Number (medium)
Solution: Kth Smallest Number
Maximum Product Subarray (medium)
Solution: Maximum Product Subarray
Same Tree (medium)
Solution: Same Tree
Max Points on a Line (hard)
Solution: Max Points on a Line
Closest Binary Search Tree Value II (hard)
Solution: Closest Binary Search Tree Value II
Word Ladder (hard)
Solution: Word Ladder
Median of Two Sorted Arrays (hard)
Solution: Median of Two Sorted Arrays
Largest Rectangle in Histogram (hard)
Solution: Largest Rectangle in Histogram
Serialize and Deserialize Binary Tree (hard)
Solution: Serialize and Deserialize Binary Tree
Solution: Valid Triangle Number

Problem Statement

Given an array of integers nums, return the number of triplets we can make using array elements that can create triangle if we take them as side lengths of a triangle.

A set of three numbers can constitute a triangle if and only if the sum of any two sides is greater than the third side. This condition must hold true for all three combinations of summed sides.

Examples

  • Example 1:

    • Input: nums = [4, 2, 3, 1]
    • Expected Output: 1
    • Justification: The valid combinations that can form a triangle are (2, 3, 4). The other combinations either do not meet the triangle inequality theorem or are duplicates in a different order.
  • Example 2:

    • Input: nums = [5, 1, 3, 4, 7]
    • Expected Output: 3
    • Justification: There are 3 combinations that meet the triangle condition, such as (3, 4, 5), (3, 5, 7), (4, 5, 7) that satisfy the triangle inequality.
  • Example 3:

    • Input: nums = [10, 21, 22, 100, 101, 200, 300]
    • Expected Output: 6
    • Justification: There are 6 combinations that meet the triangle condition, such as (10, 21, 22), (10, 100, 101), (21, 100, 101), (22, 100, 101), (100, 101, 200), and (101, 200, 300) that satisfy the triangle inequality.

Solution

To solve this problem, the most efficient approach involves sorting the input array and then using a two-pointer technique to count the triplets that satisfy the triangle inequality condition. Sorting the array allows us to apply the triangle inequality theorem more efficiently since we only need to check if the sum of the two smallest sides is greater than the largest side in a triplet. Once sorted, we iterate through the array, fixing one side as the longest side and using two pointers to find the other two sides of potential triangles.

This approach works because, for any sorted triplet where a <= b <= c, if a + b > c, then we know we have a valid triangle. By starting with the largest possible 'c' and finding 'a' and 'b' that meet the condition, we ensure that all possible combinations are accounted for without unnecessary repetition or missing any valid triplets.

Step-by-Step Algorithm

  1. Sort the Input Array:

    • Begin by sorting the array in non-decreasing order. This is crucial because it allows us to use the triangle inequality theorem effectively, knowing that if nums[i] + nums[j] > nums[k], then any j' > j will also satisfy nums[i] + nums[j'] > nums[k], reducing the number of comparisons needed.
  2. Initialize Count:

    • Set a counter variable count to 0. This will hold the number of valid triangles found.
  3. Iterate through the Array with Three Pointers:

    • Use three pointers i, j, and k to iterate through the array. The pointer i starts from 0 to nums.length - 3, j starts from i + 1 to nums.length - 2, and k = i + 2 is used to find the first element that violates the triangle condition.
  4. Find Valid Triangles:

    • For each fixed i and j, move k to find the first index where nums[i] + nums[j] <= nums[k]. The idea is that for each pair of i and j, any k between j + 1 and k - 1 (inclusive) will form a valid triangle, because nums[i] + nums[j] will be greater than nums[k] for those values, satisfying the triangle inequality theorem.
  5. Update Count:

    • For each pair of i and j, add k - j - 1 to count. This represents the number of valid triangles formed with i and j as two sides.
  6. Return the Count:

    • After iterating through all possible combinations, return the value of count.

Algorithm Walkthrough

Let's consider the Input: nums = [10, 21, 22, 100, 101, 200, 300].

  1. Sort the array: The input array is already sorted, so we proceed with it as [10, 21, 22, 100, 101, 200, 300].

  2. Initialize variables: Start with count = 0. We will update this count as we find valid triangles.

  3. Iterate through the array with three pointers (i, j, k):

    • The idea is to fix the smallest side nums[i] and find pairs nums[j] and nums[k] that satisfy the triangle inequality: nums[i] + nums[j] > nums[k].
  4. For i = 0 (nums[i] = 10):

    • Set j = i + 1 (j = 1, nums[j] = 21) and start the search for k.

    • Since k is initially set to i + 2, we start with k = 2.

    • Finding valid triangles:

      • When j = 1 (nums[j] = 21) and k = 2 (nums[k] = 22), the triangle inequality holds (10 + 21 > 22), so we increment k to find the next valid k.
      • Unable to find more valid k for this j, we move to the next j.
    • No additional valid triangles found for this i and j.

    • Update count = count + k - j - 1 = 0 + 3 - 1 - 1 = 1.

    • Update j to 2:

    • No valid triangles are found for i = 1, and j = 2.

    • For j = 3:

    • nums[0] + nums[3] > nums[4]. So, increment k to 5.

    • Update count = count + k - j - 1 = 1 + 5 - 3 - 1 = 2.

  5. For i = 1 (nums[i] = 21):

    • For j = 2 (nums[j] = 22): No valid k because 22 + 21 cannot be greater than any subsequent number in the sorted list.
    • For j = 3 (nums[j] = 100):
      • The triangle inequality holds for k = 4 (nums[k] = 101) since 21 + 100 > 101. Update k = 5.
      • Update count = count + k - j - 1 = 2 + 5 - 3 - 1 = 3.
      • Continue incrementing j and complete the next iterations.
  6. For i = 2 (nums[i] = 22):

    • For j = 3 (nums[j] = 100):
      • Similarly, the triangle inequality holds for k = 4 (nums[k] = 101) since 22 + 100 > 101. Update k = 5.
      • Update count = count + k - j - 1 = 3 + 5 - 3 - 1 = 4.
      • Continue incrementing j and complete the next iterations.
  7. For i = 3 (nums[i] = 100):

    • For j = 4 (nums[j] = 101):
      • k = 5 (nums[k] = 200) satisfies 100 + 101 > 200. Update k = 6.
      • Update count = count + k - j - 1 = 4 + 6 - 4 - 1 = 5.
      • Continue incrementing j and complete the next iterations.
  8. For i = 4 (nums[i] = 101):

    • For j = 5 (nums[j] = 200):
      • k = 6 (nums[k] = 300) satisfies 101 + 200 > 300. Update k = 7.
      • Update count = count + 7 - j - 1 = 5 + 7 - 5 - 1 = 6.
  9. Final Result:

    • Total valid triplates are 6.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity

  • Sorting: The initial sort operation has a time complexity of , where (N) is the number of elements in the input array.
  • Finding Triplets: After sorting, the algorithm iterates over each element, using two pointers to find valid triangles. The outer loop runs in time, and for each iteration of the outer loop, the inner loop can iterate up to (N) times in the worst case. However, due to the two-pointer technique, each element is visited only once by the inner loop and the (k) pointer, resulting in an overall time complexity for this part.

Combining these parts, the total time complexity of the algorithm is = , as the term dominates for large (N).

Space Complexity

  • Sorting Space: The space complexity of sorting is .
  • Auxiliary Space: Apart from the space used for sorting, the algorithm only uses a constant amount of extra space for variables, resulting in an overall auxiliary space complexity of .

Therefore, the total space complexity of the algorithm is , primarily due to the sorting operation.

Valid Triangle Number (medium)
Valid Parenthesis String (medium)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity

Space Complexity